package algorithms.sedgewick.part1.sort;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.ObjectInputStream.GetField;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeMap;


public class Fast {
	private static final String DELIM = " -> ";
	private static Map<Point, Set<Double>> slopesAlreadyConsideredForPoints;

	public static void main(String[] args) throws IOException {
		if(args==null ||
				args.length<1){
			throw new IllegalArgumentException();
		}
		System.out.println(Double.compare(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY));
		StdDraw.setXscale(0, 32768);
		StdDraw.setYscale(0, 32768) ;
		BufferedReader br = new BufferedReader(new FileReader(args[0]));
		int noOfPairs = Integer.parseInt(br.readLine().trim());
		String str;
		List<Point> pointList = new ArrayList<Point>(noOfPairs);
		Scanner scan;
		while((str = br.readLine())!=null){
			try{
				scan = new Scanner(str);
				//strArr = str.split("[\\s\\t]");
				//pointList.add(new Point(Integer.parseInt(strArr[0].trim()), Integer.parseInt(strArr[1].trim())));
				pointList.add(new Point(scan.nextInt(), scan.nextInt()));
				scan.close();
			}catch(RuntimeException r){}
		}
		br.close();

		for(Point p:pointList){
			p.draw();
		}
		Collections.sort(pointList);
		/*	for(Point p:pointList){
			System.out.println(p);
		}*/
		slopesAlreadyConsideredForPoints = new TreeMap<Point, Set<Double>>();
		findCollinearSegments(pointList);
	}
	private static final void findCollinearSegments(List<Point> pointList){
		List<Point> collinearList;
		Point origin;
		double initSlope ;
		Point target;

		List<Point> clonedList;
		for(int j=0;j<pointList.size();j++){
			clonedList= new ArrayList<Point>(pointList);
			initSlope = Double.NEGATIVE_INFINITY;
			collinearList = new ArrayList<Point>();			 
			origin = pointList.get(j);
			//System.out.println("Origin:"+origin);
			collinearList.add(origin);
			Collections.sort(clonedList, origin.SLOPE_ORDER);

			for(int i=0;i<clonedList.size();i++){
				//System.out.println("Slope:"+initSlope);
				target = clonedList.get(i);							
				if(target.compareTo(origin)<=0){
					continue;
				}

				if(origin.slopeTo(target) == initSlope){
					collinearList.add(target);
				}
				else{
					if(collinearList.size()==1){
						//add 2 points to define slope
						collinearList.add(target);
					}else{
						printAndDrawCollinearPoints(collinearList);
						collinearList = new ArrayList<Point>();	
						collinearList.add(origin);
						collinearList.add(target);
					}				
				}
				initSlope = origin.slopeTo(target);
			}
			printAndDrawCollinearPoints(collinearList);
		}
	}
	private static final void printAndDrawCollinearPoints(List<Point> collinearList){
		if(collinearList.size()>=4){
			Point lastPoint = collinearList.get(collinearList.size()-1);
			boolean isNewSlopeBeingAdded;
			//making use of the fact that there will be only one line passing through a point
			//with a particular slope. Track the slope and never print the same line again
			//anyhow largest segment will be printed.
			Set<Double> alreadyConsideredSlopes;
			if((alreadyConsideredSlopes = slopesAlreadyConsideredForPoints.get(lastPoint)) == null){
				alreadyConsideredSlopes = new HashSet<Double>();
				slopesAlreadyConsideredForPoints.put(lastPoint, alreadyConsideredSlopes);
			}
			isNewSlopeBeingAdded = alreadyConsideredSlopes.add(getSlopeForCollinearList(collinearList));
			if(!isNewSlopeBeingAdded){
				return;
			}
			StringBuilder builder = new StringBuilder();
			for(Point p:collinearList){			
				builder.append(p);
				builder.append(DELIM);
			}
			collinearList.get(0).drawTo(lastPoint);
			builder.setLength(builder.length()-DELIM.length());
			System.out.println(builder);
		}
	}
	private static final double getSlopeForCollinearList(List<Point> collinearList){
		return collinearList.get(0).slopeTo(collinearList.get(1));
	}
}
